import com.sun.deploy.util.StringUtils;
import org.junit.Test;

import java.util.LinkedList;

public class leetCodeResult0929 {

    @Test
    public void test() {
        String word1 = "ABCABC";
        String word2 = "ABC";
        System.out.println(gcdOfStrings(word1, word2));
    }

    /**
     * 1768. 交替合并字符串
     * 简单
     * 相关标签
     * premium lock icon
     * 相关企业
     * 提示
     * 给你两个字符串 word1 和 word2 。请你从 word1 开始，通过交替添加字母来合并字符串。如果一个字符串比另一个字符串长，就将多出来的字母追加到合并后字符串的末尾。
     *
     * 返回 合并后的字符串 。
     */
    public String mergeAlternately(String word1, String word2) {
        int minStrLength = Math.min(word1.length(), word2.length());
        StringBuilder stringBuffer = new StringBuilder();
        for (int i = 0; i < minStrLength; i++) {
            stringBuffer.append(word1.charAt(i));
            stringBuffer.append(word2.charAt(i));
        }
        if (word1.length() > minStrLength) {
            for (int i = minStrLength; i < word1.length(); i++) {
                stringBuffer.append(word1.charAt(i));
            }
        }
        if (word2.length() > minStrLength) {
            for (int i = minStrLength; i < word2.length(); i++) {
                stringBuffer.append(word2.charAt(i));
            }
        }
        return stringBuffer.toString();
    }

    /**XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
     * if条件判断太多的算法以后能不用就不用,太容易疏漏测试案例了，写到最后就是打补丁，代码要没法看了
     * XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
     * 1071. 字符串的最大公因子
     * 简单
     * 相关标签
     * premium lock icon
     * 相关企业
     * 提示
     * 对于字符串 s 和 t，只有在 s = t + t + t + ... + t + t（t 自身连接 1 次或多次）时，我们才认定 “t 能除尽 s”。
     *
     * 给定两个字符串 str1 和 str2 。返回 最长字符串 x，要求满足 x 能除尽 str1 且 x 能除尽 str2 。
     */
    public String gcdOfStringsXXXXXXXXXXXXX(String str1, String str2) {
        if (str1.charAt(0) != str2.charAt(0)) {
            return "";
        }
        if (str1.equals(str2)) {
            return str1;
        }
        String otherStr = "";
        String catStr = "";
        String shortStr = "";
        //将两个字符串依据较短的字符串长度分割为三个字符串
        if (str1.length() > str2.length()) {
            otherStr = str1.substring(str2.length());
            catStr = str1.substring(0, str2.length());
            shortStr = str2;
        }
        if (str1.length() < str2.length()) {
            otherStr = str2.substring(str1.length());
            catStr = str2.substring(0, str1.length());
            shortStr = str1;
        }
        //判断shortStr和catStr和otherStr是否完全一致
        if (!shortStr.equals(catStr)) {
            return "";
        }
        char firstKey = str1.charAt(0);//最大公约字符串的第一个字符
        int maxLength = 0;//可能的最大公约字符串的长度
        int maxStrLength = 0;//最大公约字符串的长度
        int begin = 0; //第二个最大公约字符串的起始位置
        boolean flag = false; //开始寻找最大公约字符串的标志
        boolean flagDo = false; //如果从来都没有开始寻找过最大公约字符串,那么字符串整体本身即为最大公约字符串
        for (int i = 0; i < shortStr.length(); i++) {
            boolean notMatch = (shortStr.charAt(i) != shortStr.charAt(maxLength));
            if (flag && !notMatch && maxLength < begin) {
                maxLength++;
            }
            //此轮寻找最大公约字符串结束
            if (flag && maxLength == begin) {
                flag = false;
                if (shortStr.length() % maxLength == 0 && (otherStr.length() % maxLength == 0 ||
                        str2.length() % maxLength == 0)) {
                    maxStrLength = Math.max(maxLength, maxStrLength);
                }
                maxLength = 0;
            }
            //出现了没有最大公约字符串的情况
            if (flag && notMatch && (i == shortStr.length() - 1 ||
                    shortStr.charAt(i + 1) != firstKey)) {
                i = begin + 1;
                flag = false;
                maxLength = 0;
            }
            if (!flag && i != 0 /*跳过第一个字符*/ && shortStr.charAt(i) == firstKey) {
                begin = i;
                flag = true;
                flagDo = true;
                maxLength++;
            }
        }
        String result = shortStr;
        if (flagDo) {
            result = shortStr.substring(0, maxStrLength);
        }
        if (maxStrLength == 0 && !shortStr.equals(otherStr)) {
            return "";
        }
        //判断最大公约字符串是否也是被切除的otherStr的最大公约字符串
        if ((flagDo && otherStr.length() % maxStrLength != 0)) {
            return "";
        }
        if (shortStr.equals(otherStr)) {
            return shortStr;
        }
        for(int i = 0; (i + maxStrLength) < otherStr.length(); i += maxStrLength){
            if (!result.equals(otherStr.substring(i, i + maxStrLength))) {
                return "";
            }
        }
        return str1.substring(0, maxStrLength);
    }

    public String gcdOfStrings(String str1, String str2) {
        //可能存在的公约数数组
        LinkedList<Integer> possibleGCDList = getGCDList(str1.length(), str2.length());
        return checkBiggestGCD(possibleGCDList, str1, str2);
    }

    private String checkBiggestGCD(LinkedList<Integer> possibleGCDList, String str1, String str2) {
        for (int i = 0; i < possibleGCDList.size(); i++) {
            String str1Gcd = str1.substring(0, possibleGCDList.get(i));
            String str2Gcd = str2.substring(0, possibleGCDList.get(i));
            if (!str1Gcd.equals(str2Gcd)) {
                continue;
            }
            int k = str1.length() / possibleGCDList.get(i);
            int j = str2.length() / possibleGCDList.get(i);
            StringBuilder str1Builder = new StringBuilder();
            for (int k1 = 0; k1 < k; k1++) {
                str1Builder.append(str1Gcd);
            }
            StringBuilder str2Builder = new StringBuilder();
            for (int j1 = 0; j1 < j; j1++) {
                str2Builder.append(str2Gcd);
            }
            if (str1Builder.toString().equals(str1) && str2Builder.toString().equals(str2)) {
                return str1Gcd;
            }
        }
        return "";
    }

    private LinkedList<Integer> getGCDList(int length, int length1) {
        LinkedList<Integer> possibleGCDList = new LinkedList<>();
        int minLength = Math.min(length, length1);
        for (int i = minLength; i > 0; i--) {
            if (length % i == 0 && length1 % i == 0) {
                possibleGCDList.add(i);
            }
        }
        return possibleGCDList;
    }
}
